package chapter01;

public class MyPow50 {
    /**
     * 快速幂 pow(x,n)
     * 递归                                        迭代
     *     x^n=(x^(n/2))^2                         2^2=4 2^(-2)=1/2 因此可以把x^n看成x^|n| 若n为负数 只需将结果取倒数
     *     ...                                     将指数变成二进制 如5->...0101
     *     x^2=(x^1)^2                             初始化 res==1  item=x
     *     x^1=x                                   从右到左遍历二进制位
     *  1).n>0                                     若为1 res乘上item res=res*item
     *      若n%2==0 x^n=(x^(n/2))^2               若为0 res无需乘item
     *      若n%!=0  x^n=x*(x^(n/2))^2             但item每次需要扩大平方 item=item*item
     *  2).n<0                                     n&1可以拿到最右边的位  n>>1可以将位数逐渐拿到
     *      若n%2==0 x^n=(x^(n/2))^2               1).细节
     *      若n%2!=0 x^n=(1/x)*(x^(n/2))^2             n==MIN_INT n转为正数会溢出
     *  递归终点                                       可以将n变成long类型 再取绝对值
     *     a).n==0
     *        return 1
     */
    public double myPow(double x, int n) {
        long m=n;
        m=Math.abs(m);
        double res=1;
        while(m>0){
            if((m&1)!=0){
                res*=x;
            }
            x*=x;
            m>>=1;
        }
        return n<0?1/res:res;
    }

    public double myPow1(double x, int n) {
        return process(x,n);
    }

    public double process(double x,int n){
        if(n==0){
            return 1;
        }
        double res=process(x,n/2);
        res*=res;
        if(n%2!=0){
            res=res*(n<0?1/x:x);
        }
        return res;
    }
}
